The invention is in the field of automatic systems for electronic classification of objects which are characterized by electronic attributes.
Such systems are used, for example, in conjunction with the manufacture of products in large piece numbers. In the course of production of an industrial mass-produced product, sensor means are used for automatically acquiring various electronic data on the properties of the manufactured products in order, for example, to check the observance of specific quality criteria. This can involve, for example, the dimensions, the weight, the temperature or the material composition of the product. The acquired electronic data are to be used to detect defective products automatically, select them and subsequently appraise them manually. The first step in this process is for historical data on manufactured products, for example on the products produced in past manufacturing processes, to be stored electronically in a database. A database accessing means of a computer installation is used to feed the historical data in the course of a classification method to a processor device which uses the historical data to generate automatically characteristic profiles of the two quality classes xe2x80x9cProduct acceptablexe2x80x9d and xe2x80x9cProduct defectivexe2x80x9d and to store them in a classifier file. What is termed a classifier is formed automatically in this way with the aid of machine learning.
During the production process for manufacturing the products to be tested and/or classified, the electronic data supplied for each manufactured product by the sensors are evaluated in the online classification mode by an online classification device on the basis of the classifier file or the classifier, and the tested product is automatically assigned to one of the two quality classes. If the class xe2x80x9cProduct defectivexe2x80x9d is involved, the appropriate product is selected and sent for manual appraisal.
A substantial problem in the case of the classifiers described by the example is currently to be found in the large number of the acquired historical data. In the course of the comprehensive networking of computer-controlled production installations or other computer installations via the Internet and Intranets, as well as the corporate centralization of electronic data, an explosive growth is currently taking place in the electronic data stocks of companies. Many databases already contain millions and billions of customer and/or product data. The processing of large data stocks is therefore playing an ever greater role in all fields of data processing, not only in conjunction with the production process outlined above. On the one hand, the information, which can be derived automatically from historical data which are present in very large numbers, is xe2x80x9cmore valuablexe2x80x9d with regard to the formation of the classifier, since a large number of historical data are used to generate it automatically, while on the other hand there exists the problem of managing the number of historical data efficiently with regard to the time expended when constructing the classifier.
Known classification methods such as described, for example, in the printed publication U.S. Pat. No. 5,640,492 are based for the most part on decision trees or neural networks. Decision trees admittedly permit automatic classification over large electronic data volumes, but generally exhibit a low quality of classification, since they treat the attributes of the data separately and not in a multivariat fashion.
The best conventional classification methods such as backpropagation networks, radial basis functions or support vector machines can mostly be formulated as regularization networks. Regularization networks minimize an error functional which comprises a weighted sum of an approximation error term and of a smoothing operator. The known machine learning methods execute this minimization over the space of the data points, whose size is a function of the number of the acquired historical data, and are therefore suitable only for historical data records which are small- to medium-sized.
It is usually necessary in this case to solve the following problem of classification and/or regression. M data points exist in a d-dimensional space xi, i=1, . . . , M, xixcex5Rd. The data points are assigned function values: yi, i=1, . . . , M, yixcex5Rd (regression) or y1xcex5{xe2x88x921; +1} (classification). The training set is therefore yielded as S={(xi, yi)xcex5RdxR}i=1M. The following regularization problem now needs to be solved:
min R(ƒ) ƒxcex5Vxe2x80x83xe2x80x83(1)
with                                           R            ⁡                          (              f              )                                -                      xe2x80x83                    ⁢                                    1              M                        ⁢                                          ∑                                  i                  =                  1                                M                            ⁢                              C                ⁡                                  (                                                            f                      ⁡                                              (                                                  x                          i                                                )                                                              ,                                          y                      i                                                        )                                                              +                      λxe2x88x85            ⁡                          (              f              )                                      ,                            (        2        )            
where
C(x,y) is an error functional, for example C(x,y)=(xxe2x88x92y)2;
xcfx86(ƒ) is a smoothing operator, "PHgr"(f)=∥Pf∥22, for example Pf=∇f;
ƒ is a regression/classification function with the required smoothness properties for the operator P; and
xcex is a regularization parameter.
The classification function ƒ usually determined in this case as a weighted sum of ansatz functions "PHgr"i over the data points:                                           f            C                    ⁡                      (            x            )                          =                              ∑                          i              =              1                        M                    ⁢                                    α              i                        ⁢                                                            ϕ                  i                                ⁡                                  (                  x                  )                                            .                                                          (        3        )            
The known approach to a solution leads essentially to two problems: (i) because of the global nature of the ansatz functions "PHgr"i and the number of coefficients xcex1i (equal to the number M of data points), the solution to the regression problem is very time-consuming and sometimes impossible for larger data volumes, since it requires the use of matrices of size Mxc3x97M; (ii) the application of the classification function ƒc to new data records in the course of online classification is very time-consuming, since summing has to be carried out over all functions "PHgr"i(i=1, . . . , M).
It is the object of the invention to create a possibility to use automatic systems for the electronic classification of objects, which are characterized by electronic attributes, even for applications in which a very large number of data points are present.
The object is achieved according to the invention by means of the independent claims.
An essential idea which is covered by the invention consists in the application of the sparse grid technique. For this purpose, the function ƒ not generated in accordance with the formulation of (3) but a discretization of the space V is undertaken, VNxcex5V being a finitely dimensioned subspace of V, and N being a dimension of the subspace VN. The function ƒ is determined as                                           f            N                    ⁡                      (            x            )                          =                              ∑                          i              =              1                        N                    ⁢                                    α              i                        ⁢                                                            ϕ                  i                                ⁡                                  (                  x                  )                                            .                                                          (        4        )            
The regularization problem in the space VN determining ƒN is then:                                           R            ⁡                          (                              f                N                            )                                =                                                    1                M                            ⁢                                                ∑                                      i                    =                    1                                    M                                ⁢                                                      (                                                                                            f                          N                                                ⁡                                                  (                                                      x                            i                                                    )                                                                    -                                              y                        i                                                              )                                    2                                                      +                          λ              ⁢                                                "LeftDoubleBracketingBar"                                      Pf                    N                                    "RightDoubleBracketingBar"                                                  L                  2                                2                                                    ,                  
                ⁢                              with            ⁢                          xe2x80x83                        ⁢                          C              ⁡                              (                                  x                  ,                  y                                )                                              =                                                                      (                                      x                    -                    y                                    )                                2                            ⁢                              xe2x80x83                            ⁢              and              ⁢                              xe2x80x83                            ⁢                              φ                ⁡                                  (                  f                  )                                                      =                                                            "LeftDoubleBracketingBar"                  Pf                  "RightDoubleBracketingBar"                                2                2                            .                                                          (        5        )            
By contrast with conventional methods, the sparse grid space is selected as subspace VN. This avoids the problems of the prior art. The number N of the coefficients xcex1i to be determined depends only on the discretization of the space V. The effort on the solution of (5) scales linearly with the number M of data points. Consequently, the method can be applied for data volumes of virtually any desired size. The classification function ƒN is built up only from N ansatz functions and can therefore be evaluated quickly in the application.
The essential advantage which the invention provides by comparison with the prior art consists in that the outlay for generating the classifier scales only linearly with the number of data points, and thus the classifier can be generated for electronic data volumes of virtually any desired size. A further advantage consists in the higher speed of application of the classifier to new data records, that is to say in the quick online classification.
The sparse grid classification method can also be used to evaluate customer, financial and corporate data.
Advantageous developments of the invention are disclosed in the dependent subclaims.